1. Technical Field of the Invention
This invention relates generally to data communications and more particularly to error detection and correction of such data communications.
2. Description of Related Art
As is known, communication systems include a plurality of communication devices (e.g., modems, cable modems, personal computers, laptops, cellular telephones, radios, telephones, facsimile machines, et cetera) that communicate directly (i.e., point-to-point) or indirectly via communication system infrastructure (e.g., wire line channels, wireless channels, bridges, switches, routers, gateways, servers, et cetera). As is also known, a communication system may include one or more local area networks and/or one or more wide area networks to support at least one of the Internet, cable services (e.g., modem functionality and television), wireless communications systems (e.g., radio, cellular telephones), satellite services, wire line telephone services, digital television, et cetera.
In any type of communication system, information (e.g., voice, audio, video, text, data, et cetera) is transmitted from one communication device to another via the infrastructure. Accordingly, the transmitting communication device prepares the information for transmission to the other device and provides the prepared information to the infrastructure for direct or indirect routing to the receiving communication device. For indirect routing, a piece of infrastructure equipment (e.g., server, router, et cetera) receives prepared information and forwards it to another piece of infrastructure equipment or to the receiving communication device. The prepared information is thus propagated through the infrastructure until it reaches the receiving communication device. Once received, the receiving communication device traverses the processing steps used by the transmitting communication device to prepare the information for transmission to recapture the original information.
As is further known, transmission of information between communication devices is not performed in an ideal environment where the received information exactly matches the transmitted information. In practice, the infrastructure introduces error, which distorts the transmitted information such that the received information does not exactly match the transmitted information. To compensate for the error introduced by the infrastructure, the transmitting communication device includes an encoder, which adds redundancy to the original data to make the original data more unique, and the receiving communication device includes a corresponding decoder, which uses the redundancy information to recover the original data from the received data that includes transmission errors.
In general, the encoder and decoder are employing an error detection and correction technique to reduce the adverse effects of transmission errors. As is known, there are a number of popular error correction techniques. One such technique is generally known as forward error correction (FEC). FEC involves an encoder generating error correction data as a function of the data to be sent and then transmitting the error correction data along with the data. A decoder within the receiving communication device utilizes the error correction data to identify any errors in the original data that may have occurred during transmission. In particular, the decoder uses the error correction data, or redundancy bits, to first determine if any error exists in the original transmitted data. If an error exists, the decoder uses the error correction data to correct the error(s), provided the number of errors are less than the maximum number of correctable errors for the given encoding/decoding scheme.
One particular type of forward error correction is called cyclic redundancy checking (CRC). CRC involves generating redundancy bits by partioning the bit stream of the original data into blocks of data. The blocks of data are processed sequentially, with the data from each block being divided by a polynomial. The remainder from the division process becomes the redundancy bits, which are appended to, and transmitted with, the block of data from which they were generated. The decoder, upon receiving a block of data, divides the block of data and the appended redundancy bits by the same polynomial. If the remainder of this division is zero, there are no errors in the received block of data. If, however, there is a remainder, an error exists. For CRC, when an error exists in the block of data, the decoder typically requests retransmission of the block of data.
Another popular FEC algorithm is called Reed Solomon encoding and decoding. Like CRC, Reed Solomon partitions a data stream into sequential blocks of data and then divides a block of data by a polynomial to obtain parity, or check, data. However, Reed Solomon operates on a byte stream rather than a bit stream, so it creates check bytes, which are appended to each block of data. The decoding process at the receiver is considerably more complex than that of the CRC algorithm. First, a set of syndromes is calculated. If the syndromes have a zero value, the received block of data is deemed to have no errors. If one or more of the syndromes are not zero, the existence of one or more errors is indicated. The non-zero values of the syndrome are then used to determine the location of the errors and, from there, correct values of data can be determined to correct the errors.
Many of the FEC schemes are based on Galois field (GF) arithmetic. For example, CRC is based on GF(2) in processing blocks of single bit data (i.e., the finite field consists of only two values, 0 and 1). Reed Solomon is based on a finite field of GF(28), which has elements that can have 256 different values (e.g., zero, 1, α, α2, . . . , α254). The Reed Solomon operation of dividing blocks of data by a polynomial includes multiply and add operations that are finite field in nature. Due to the unique nature of Galois field arithmetic, Reed Solomon encoders and/or decoders may be implemented using digital signal processors (DSP) and/or microprocessors that include special hardware to perform the requisite Galois field mathematical operations of error correction algorithms.
In particular, Galois field addition can be effectively implemented using an exclusive OR logic function between two elements that are to be added. However, multiplication and division are much more complex. Prior art solutions have employed look-up tables, as the special hardware, to perform GF multiplications using otherwise traditional DSP and microprocessor computational resources. Table look-up operations are very slow and therefore not very desirable, particularly when an application is being performed that requires the error correction operations to be completed in real time on high-speed data.
Therefore, a need exists for a processor that includes a finite field arithmetic unit that is capable of performing multiple finite field arithmetic functions and/or finite field based applications.